Given a string s, return the length of the longest substring that contains at most two distinct characters.
Example 1:
Input: s = "eceba" Output: 3 Explanation: The substring is "ece" which its length is 3.
Example 2:
Input: s = "ccaabbb" Output: 5 Explanation: The substring is "aabbb" which its length is 5.
Constraints:
1 <= s.length <= 104sconsists of English letters.
Average Rating: 4.88 (60 votes)
Video Solution
Solution Article
Approach 1: Sliding Window
Intuition
To solve the problem in one pass
let's use here sliding window approach with two set pointers
left and right serving as the window boundaries.
The idea is to set both pointers in the position 0 and
then move right pointer to the right while the
window contains not more than two distinct characters.
If at some point we've got 3 distinct characters,
let's move left pointer to keep not more than 2
distinct characters in the window.
Basically that's the algorithm : to move sliding window along the string,
to keep not more than 2 distinct characters in the window, and
to update max substring length at each step.
There is just one more question to reply - how to move the left pointer to keep only
2distinct characters in the string?
Let's use for this purpose hashmap containing all characters
in the sliding window as keys and their rightmost positions
as values. At each moment, this hashmap could contain
not more than 3 elements.
For example, using this hashmap one knows that the rightmost position
of character e in "eeeeeeeet" window is 8 and so one has
to move left pointer in the position 8 + 1 = 9 to
exclude the character e from the sliding window.
Do we have here the best possible time complexity?
Yes, we do - it's the only one pass along the string with
N characters and the time complexity is O(N).
Algorithm
Now one could write down the algortihm.
- Return
Nif the string lengthNis smaller than3. - Set both set pointers in the beginning
of the string
left = 0andright = 0and init max substring lengthmax_len = 2. - While
rightpointer is less thanN:- If hashmap contains less than
3distinct characters, add the current characters[right]in the hashmap and moverightpointer to the right. - If hashmap contains
3distinct characters, remove the leftmost character from the hashmap and move theleftpointer so that sliding window contains again2distinct characters only. - Update
max_len.
- If hashmap contains less than
Implementation
Complexity Analysis
-
Time complexity : O(N) where
Nis a number of characters in the input string. -
Space complexity : O(1) since additional space is used only for a hashmap with at most
3elements.
Problem generalization
The same sliding window approach could be used to solve the generalized problem :
June 16, 2019 10:03 AM
Why is this problem classified as hard?
November 23, 2020 3:17 AM
The video solution is really well articulated! Loved the approach and simplicity.
Last Edit: February 14, 2019 7:07 AM
less branchy approach would be put str[right] unconditionally and shirking the windows by increment left while size>2 O(N) time and O(2) space for hashmap
int lengthOfLongestSubstringTwoDistinct(string str) {
int ans=0;
unordered_map<char,int> count;
int l=0, r=0, N=str.length();
while (r<N) {
count[str[r]]++;
while (count.size()>2 && r>=l) {
count[str[l]]--;
if (count[str[l]]==0)
count.erase(str[l]);
l++;
}
ans=max(ans,r-l+1);
r++;
}
return ans;
}
May 25, 2020 7:45 AM
I found this statement confusing "delete the leftmost character". Its actually not considering the left most character in the sliding window but in hash map(after sorting based on last seen index of the character). For example "eceba" is the given input. If we just consider the first character inserted in hash map then actually 'e' will be removed when encounter more than 2 distinct characters in string. But in fact we remove 'c' from hash map.
November 27, 2020 11:46 AM
How does finding the minimum value in a hashmap take less than linear time?
January 8, 2020 4:16 AM
Python Time O(n) and Space O(1) no hashmap
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
last_char = ''
second_last_char = ''
last_char_count = 0
maximum = 0
currentMax = 0
for char in s:
if char == last_char or char == second_last_char:
currentMax +=1
else:
currentMax = last_char_count + 1
if char == last_char:
last_char_count += 1
else:
last_char_count = 1
second_last_char = last_char
last_char = char
maximum = max(currentMax, maximum)
return maximum
February 16, 2019 12:22 AM
Why does the python solution use defaultdict instead of a regular dict?
February 16, 2019 4:06 AM
i know which company uses this question , lol
May 19, 2019 7:22 AM
Isn't determining the length of the hashmap, O(n)? So the time complexity of this solution would not be O(n).
February 16, 2019 4:43 PM
using only one array solution:
public static int kUnique(String str, int k){
k=2; // remove k=2 for k unique characters
int start=0, maxlength=0, uniquecount=0;
int[] hash = new int[256];
Arrays.fill(hash, 0);
for (int i =0; i< str.length(); i++){
if (uniquecount < k){
if (hash[str.charAt(i)] == 0) {
hash[str.charAt(i)]++;
uniquecount++;
}
else {
hash[str.charAt(i)]++;
}
}
else{
if (hash[str.charAt(i)]>0){
hash[str.charAt(i)]++;
}
else {
while (uniquecount >= k){
hash[str.charAt(start)]--;
if (hash[str.charAt(start)]==0){
uniquecount--;
}
start++;
}
if (hash[str.charAt(i)]==0){
hash[str.charAt(i)]++;
uniquecount++;
}
}
}
maxlength = Math.max(maxlength, i - start +1);
}
if (uniquecount<k){
return -1;
}
return maxlength;
}
x
class Solution {public: int lengthOfLongestSubstringTwoDistinct(string s) { unordered_map<char,int>mp; int res = 0; for(int i=0,j=0;j<s.length();j++) { mp[s[j]]++; while(mp.size() > 2) { mp[s[i]]--; if(mp[s[i]] == 0) mp.erase(s[i]); i++; } res = max(res, j-i+1); } return res; }};